A subgraph of an edge-coloured complete graph is called rainbow if all itsedges have different colours. The study of rainbow decompositions has a longhistory, going back to the work of Euler on Latin squares. In this paper wediscuss three problems about decomposing complete graphs into rainbow trees:the Brualdi-Hollingsworth Conjecture, Constantine's Conjecture, and theKaneko-Kano-Suzuki Conjecture. We show that in every proper edge-colouring of$K_n$ there are $10^{-6}n$ edge-disjoint spanning isomorphic rainbow trees.This simultaneously improves the best known bounds on all these conjectures.Using our method we also show that every properly $(n-1)$-edge-coloured $K_n$has $n/9$ edge-disjoint rainbow trees, giving further improvement on theBrualdi-Hollingsworth Conjecture.
展开▼
机译：如果边缘的完整图的所有边缘具有不同的颜色，则将其称为彩虹。彩虹分解的研究源远流长，可追溯到欧拉在拉丁方格上的工作。在本文中，我们讨论了将完整图分解为彩虹树的三个问题：布鲁拉迪-霍林斯沃思猜想，君士坦丁猜想和金奈子-卡诺-铃木猜想。我们证明，在$ K_n $的每一个合适的边缘着色中，都有$ 10 ^ {-6} n $个边缘不相交的同构彩虹树，这同时改善了所有这些猜想的最著名边界。使用我们的方法，我们还证明了每一个适当的（n-1）$边缘色$ K_n $都有$ n / 9 $边缘不交织的彩虹树，这进一步改善了布卢迪-霍林斯沃思猜想。
展开▼
